package org.leetcode.middle.leetcode199;

import org.leetcode.TreeNode;

import java.util.*;

public class Solution
{
    public List<Integer> rightSideView(TreeNode root) {
       List<Integer> res = new ArrayList<>();
        checkFun(root,res);
        return res;
    }

    /**
     * 层序遍历，然后保留每一层最后一个元素
     */
    public void checkFun(TreeNode node, List<Integer> res)
    {
        if (node==null)
        {
            return;
        }

        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(node);

        while (!queue.isEmpty())
        {

            int length = queue.size();

            List<Integer> listOne = new ArrayList<>();
            while (length>0)
            {
                TreeNode tempNode= queue.poll();
                listOne.add(tempNode.val);

                if (tempNode.left!=null) queue.add(tempNode.left);
                if (tempNode.right!=null) queue.add(tempNode.right);
                length--;
            }

            res.add(listOne.get(listOne.size()-1));
        }
    }

    /**
     * 官方题解
     */
    public List<Integer> rightSideView2(TreeNode root) {
        Map<Integer, Integer> rightmostValueAtDepth = new HashMap<Integer, Integer>();
        int max_depth = -1;

        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
        Queue<Integer> depthQueue = new LinkedList<Integer>();
        nodeQueue.add(root);
        depthQueue.add(0);

        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.remove();
            int depth = depthQueue.remove();

            if (node != null) {
                // 维护二叉树的最大深度
                max_depth = Math.max(max_depth, depth);

                // 由于每一层最后一个访问到的节点才是我们要的答案，因此不断更新对应深度的信息即可
                rightmostValueAtDepth.put(depth, node.val);

                nodeQueue.add(node.left);
                nodeQueue.add(node.right);
                depthQueue.add(depth + 1);
                depthQueue.add(depth + 1);
            }
        }

        List<Integer> rightView = new ArrayList<Integer>();
        for (int depth = 0; depth <= max_depth; depth++) {
            rightView.add(rightmostValueAtDepth.get(depth));
        }

        return rightView;
    }

    public static void main(String[] args) {
        // 创建节点
//        TreeNode node9 = new TreeNode(9);
//        TreeNode node8 = new TreeNode(8);
//        TreeNode node7 = new TreeNode(7);
//        TreeNode node6 = new TreeNode(6);
//        TreeNode node5 = new TreeNode(5, node8, node9);
//        TreeNode node4 = new TreeNode(4);
//        TreeNode node3 = new TreeNode(3);
//        TreeNode node2 = new TreeNode(2, node4,null);
//        TreeNode node1 = new TreeNode(1, node2, node3); // 根节点
//
//        LRUCache solution = new LRUCache();
//        solution.rightSideView2(node1);

        List<Integer> list =new ArrayList<>();

        list.add(1);
        list.add(2);
        list.add(3);

        System.out.println(list.get(list.size()-1));

//        Collections.reverse(list);
//
//        System.out.println(list);
    }

}
